Your browser doesn't support the features required by impress.js, so you are presented with a simplified version of this presentation.
For the best experience please use the latest Chrome , Safari or Firefox browser.
\[
\newcommand{\IR}{\mathbb{R}}
\newcommand{\IRnn}{\IR_{\geq 0}}
\newcommand{\IRp}{\IR_{\gt 0}}
\newcommand{\IN}{\mathbb{N}}
\newcommand{\INo}{\IN_0}
\newcommand{\INs}{\IN^\ast}
\newcommand{\coloneqq}{\mathbin{:=}}
\newcommand{\eqqcolon}{\mathbin{=:}}
\newcommand{\coloniff}{\mathbin{:\!\!\iff}}
\newcommand{\dcup}{\mathbin{\dot\cup}}
\newcommand{\sMid}{\,|\,}
\newcommand{\Set}[1]{\left\lbrace#1\right\rbrace}
\newcommand{\SMid}{\,\middle|\,}
\newcommand{\abs}[1]{\lvert#1\rvert}
\newcommand{\Abs}[1]{\left\lvert#1\right\rvert}
\newcommand{\norm}[1]{\lVert#1\rVert}
\newcommand{\Norm}[1]{\left\lVert#1\right\rVert}
\newcommand{\PSet}[1]{2^{#1}}
\newcommand{\bigO}{\mathcal{O}}
\newcommand{\transp}{^\top}
\newcommand{\eps}{\varepsilon}
\newcommand{\classFP}{\mathrm{FP}}
\newcommand{\classFNP}{\mathrm{FNP}}
\newcommand{\classFNPC}{\mathrm{FNPC}}
\newcommand{\classTFNP}{\mathrm{TFNP}}
\newcommand{\classPPAD}{\mathrm{PPAD}}
\newcommand{\classPLS}{\mathrm{PLS}}
\newcommand{\SocOptPNEinUnwCong}{\style{font-variant-caps:small-caps}{\text{SocOptPNEinUnwCong}\hspace{1em}}}
\newcommand{\HamiltonCycle}{\style{font-variant-caps:small-caps}{\text{HamiltonCycle}\hspace{1em}}}
\newcommand{\LocalMaxCut}{\style{font-variant-caps:small-caps}{\text{LocalMaxCut with Flip-Neighbourhood}\,}}
\newcommand{\plInitk}{{\color{var(--plInitkCol)}\mathrm{Init}^k}}
\newcommand{\plTriggerk}{{\color{var(--plTriggerkCol)}\mathrm{Trigger}^k}}
\newcommand{\plTriggerkp}{{\color{var(--plTriggerkpCol)}\mathrm{Trigger}^{k+1}}}
\newcommand{\plPlayerAk}{{\color{var(--plPlayerAkCol)}\mathrm{Player}_1^k}}
\newcommand{\plPlayerBk}{{\color{var(--plPlayerBkCol)}\mathrm{Player}_2^k}}
\newcommand{\plStart}{{\color{var(--plStartCol)}\mathrm{Start}}}
\]
§4 Congestion Games
finite set of players $N$
finite set of resources $R$
sets of strategies $S_i \subseteq \IR^R$
$\ell: S \to \IR^R, s \mapsto \ell(s) \coloneqq \sum_{i \in N}s_i$ load/congestion vector
player specific, load-dependent, per-unit resource costs $c_i: \IR^R \to \IR^R$
players' cost functions $\pi_i: S \to \IR, s \mapsto s_i\transp c_i(\ell(s)) = \sum_{r \in R}s_{i,r}c_{i,r}(\ell(s))$
⤳ generic congestion game $(N,S,\pi)$ (cost minimization game!)
N = \{
\color{var(--pl1col)}1
\color{var(--pl2col)}2
\}
\color{var(--pl1col)}S_1 = \{\hspace{1.2cm},\hspace{1.2cm}\class{tempstep}{\data{tempstep-classes=13-100:inactive}{\}}}
\color{var(--pl2col)}S_2 = \{\hspace{1.2cm},\hspace{1.2cm}\}
\color{gray}r_1
\color{gray}r_2
\color{gray}r_3
\color{gray}r_4
\color{black}\ell_{r_2}
\small\color{black}c_{r_2,\color{var(--pl1col)}1}(\ell(s))
\color{black}\cdot
unweighted congestion game $\coloniff S_i \subseteq \set{0,1}^R$ $\coloniff S_i \subseteq \set{0,d_i}^R$ player-independent/homogeneous costs $\coloniff \forall i,j \in N: c_i = c_j$ $\coloniff \ell_r(s) = \ell_r(s') \implies c_{i,r}(\ell(s)) = c_{i,r}(\ell(s'))$
\small\color{var(--pl2col)}o_2
\small\color{var(--pl1col)}o_1
\small\color{var(--pl2col)}d_2
\small\color{var(--pl1col)}d_1
\small\color{black}4+x
\small\color{black}1
\small\color{black}1+x^2
\small\color{black}1
\small\color{black}1
\small\color{black}x
\small\color{black}3+2x
$D=(V,E)$
$R=E$
§4.2 Unweighted Congestion Games
Here: Only unweighted congestion games (with separable, homog. cost functions) ⤳ have resource cost functions $c_r: \INo \to \IR$ and ⤳ set of resources used by player $i$ (under $s_i$) $R(s_i) \coloneqq \set{r \in R \sMid s_{i,r} = 1}$⤳ $\pi_i(s) = \sum_{r \in R(s_i)}c_r(\ell_r(s)) = \sum_{r \in R(s_i)}c_r(\abs{\set{j \in N \sMid r \in R(s_j)}})$
Thm. 4.5: Every unweighted congestion game has a pure NE.
Thm. 4.5: Every unweighted congestion game is exact potential game.
Rosenthal potential $P(s) \coloneqq \sum_{r \in R}\sum_{k=1}^{\ell_r(s)}c_r(k)$
Thm. 4.13: Every exact potential game is isomorphic to unweighted congestion game.
games $G=(N,S,u)$, $H=(N,T,v)$ are isomorphic if $\exists \phi_i: S_i \to T_i$ bijections s.th.
$\forall i \in N, s \in S: u_i(s) = v_i(\phi_1(s_1), \dots, \phi_n(s_n))$.
Thm. 3.10: $G$ has exact potential iff $\exists G^C=(N,S,u^C), G^D=(N,S,u^D)$ s.th. $G=G^C+G^D$, i.e., $u_i = u^C_i + u^D_i$, and
$G^C$ coordination game , i.e., $u^C_i = u_j^C$
$G^D$ dummy game , i.e., $u^D(.,s_{-i}) = \mathrm{const.}$
Lem. 4.8: Every coordination game is isomorphic to unweighted congestion game
Lem. 4.10: Every dummy game is isomorphic to unweighted congestion game
coord. game $G=(N,S,u)$ $\mapsto$ cong. game $H=(N,T,\pi)$:
$R \coloneqq S$
$R(T_i) \coloneqq \Set{\bigcup_{s_{-i} \in S_i}\set{(s_i,s_{-i})} \SMid s_i \in S_i}$
$c_s(k) \coloneqq \begin{cases}u_i(s) \text{ for any } i \in N, &\text{if } k = n\\0, &\text{else}\end{cases}$
dummy. game $G=(N,S,u)$ $\mapsto$ cong. game $H=(N,T,\pi)$:
$R \coloneqq \bigcup_{i \in N}S_{-i}$
$R(T_i) \coloneqq \Set{S_{-i} \cup \bigcup_{j \neq i}\set{s'_{-j} \in S_{-j} \sMid s_i' \neq s_i} \SMid s_i \in S_i}$
$c_{s_{-i}}(k) \coloneqq \begin{cases}u_i(s_i,s_{-i}) \text{ for any } s_i \in S_i, &\text{if } k = 1\\0, &\text{else}\end{cases}$
\class{TLtext}{\small TL}
\class{TCtext}{\small TC}
\class{TRtext}{\small TR}
\class{BLtext}{\small BL}
\class{BCtext}{\small BC}
\class{BRtext}{\small BR}
\small\color{var(--stratTcol)}\phi_1(T)
\small\color{var(--stratBcol)}\phi_1(B)
\small\color{var(--stratLcol)}\phi_2(L)
\small\color{var(--stratCcol)}\phi_2(C)
\small\color{var(--stratRcol)}\phi_2(R)
0
1
2
2
3
4
\class{Ttext}{\small T\_}
\class{Btext}{\small B\_}
\class{Ltext}{\small \_L}
\class{Ctext}{\small \_C}
\class{Rtext}{\small \_R}
\small\color{var(--stratTcol)}\phi_1(T)
\small\color{var(--stratBcol)}\phi_1(B)
\small\color{var(--stratLcol)}\phi_2(L)
\small\color{var(--stratCcol)}\phi_2(C)
\small\color{var(--stratRcol)}\phi_2(R)
2
3
0
1
3
Computing Pure Nash Equilibria in Congestion Games
Improving-Moves Algorithm
Input: finite game $G=(N,S,\pi)$, profile $s \in S$
Output: A PNE $s^\ast \in S$ of $G$
While $s$ is not a PNE Do mm choose $i \in N$ and $s'_i \in S_i$ with $\pi_i(s'_i,s_{-i}) \lt \pi_i(s)$mm set $s \leftarrow (s'_i,s_{-i})$Return $s$
Thm 4.15: For each $n \in \IN$ there exists an unweighted congestion game with
$\bigO(n)$ players with 2 strategies each
$\bigO(n)$ resources with non-negative, non-decreasing cost functions
such that Improving-Moves can take $\Omega(2^n)$ steps.
Define unweighted congestion game $G^n=(N,S,\pi)$:
$6n$ resources $r^k_j$ for $k \in \set{0,\dots,n-1}, j \in \set{0,\dots,5}$
$4n+1$ players: $\plInitk$, $\plTriggerk$, $\plPlayerAk$ and $\plPlayerBk$ for $k \in \set{0,1\dots,n-1}$ and $\plStart$
\color{gray}?
\color{gray}\dots
\color{gray}r^{k+1}_3
\color{gray}r^{k}_0
\color{gray}r^{k}_2
\color{gray}r^{k}_1
\color{gray}r^{k}_5
\color{gray}r^{k}_4
\color{gray}r^{k}_3
\color{gray}r^{k-1}_0
\color{gray}\dots
strategies: $\plInitk$ $\color{var(--plInitkCol)}\set{\class{plInitstP}{\set{r^k_0}},\class{plInitstA}{\set{r^k_1,r^k_2}}}$ $\plTriggerk$ $\color{var(--plTriggerkCol)}\set{\class{plTriggerstP}{\set{r^k_1}},\class{plTriggerstA}{\set{r^k_3,r^{k-1}_0}}}$ $\plPlayerAk$ $\color{var(--plPlayerAkCol)}\set{\class{plPlayerAstP}{\set{r^k_2}},\class{plPlayerAstA}{\set{r^k_3,r^k_4}}}$ $\plPlayerBk$ $\color{var(--plPlayerBkCol)}\set{\class{plPlayerBstP}{\set{r^k_4}},\class{plPlayerBstA}{\set{r^k_1,r^k_5}}}$ $\plStart$ $\color{var(--plStartCol)}\set{\class{plStartstP}{\set{r^{n-1}_0}}}$
$c_r(1)$
$2^{20(k+1)+6}$
$2^{20k}$
$2^{20k+4}$
$2^{20k+2}$
$2^{20k+10}$
$2^{20k+8}$
$2^{20k+6}$
$2^{20(k-1)}$
$c_r(2)$
$2^{20(k+1)+10}$
$2^{20k+20}$
$2^{20k+18}$
$2^{20k+8}$
$2^{20k+16}$
$2^{20k+10}$
$2^{20(k-1)+20}$
$c_r(3)$
$2^{20k+14}$
Obs: All deviations are even best-responses!
The Complexity of Computing PNE in Unweighted Congestion Games
Input
finite $n$-player game with
finite 2-player game with
unweighted $n$-player congestion game with
Output
PNE
MNE
PNE
Algorithm
BR-marking
Full Support Enumeration / Lemke-Howson
BR-marking / Improving Moves
Runtime
$\bigO(n\cdot\abs{S})$
$\bigO(2^{\abs{S}})$
$\bigO(n\cdot\abs{S}^2)$
Complexity Class
$\classFP$
$\classPPAD$ -complete?
$\SocOptPNEinUnwCong$: Input: unweighted congestion game $G$, number $k \in \IN$Question: $\exists$ PNE in $G$ with social cost $\leq k$?
$\HamiltonCycle$: Input: undirected graph $D=(V,E)$Question: $\exists$ cycle in $D$ visiting each vertex exactly once?
Thm 4.19: $\SocOptPNEinUnwCong$ is NP-complete.
*
via $\HamiltonCycle \leq \SocOptPNEinUnwCong$
\color{black}\large \classFNP
\color{black}\large \classFP
\color{black}\large \classFNPC
\color{black}\large \classTFNP
\color{black}\large \classPPAD
\color{black}\large \classPLS
local search problem $\Pi$ has for any instance $I \in \Pi$:
set of feasible solution $S_I$
objective function $c_I: S_I \to \IR$
for any $s \in S_I$ a neighbourhood $N_I(s) \subseteq S_I$
Goal: Find $s^* \in S_I: \forall s' \in N_I(s^*): c_I(s') \geq c_I(s^*)$ (local minimum )⤳ transition graph $(S_I,E_I)$ with $(s,s') \in E_i \coloniff s' \in N_I(s) \land c_I(s) \gt c_I(s')$ $\Pi \in \classPLS$ (polynomial local search) if f.a. $I \in \Pi$ we can compute in polynomial time:
some feasible solution $s^0 \in S_I$
$c_I(s)$ for any $s \in S_I$
for any $s \in S_I$ either $s' \in N_I(s)$ with $c_I(s') \lt c_I(s)$ or decide local optimality
$\Pi' \leq \Pi$ if there are polynomial time computable functions $f,g$ such that
$f: \Pi' \to \Pi, I \mapsto f(I)$ and
$g: S_{f(I)} \to S_I$ s.th. $s' \in S_{f(I)}$ loc. opt. for $f(I) \implies g(s') \in S_I$ loc. opt for $I$
$\Pi$ $\classPLS$-complete if $\Pi \in \classPLS$ and $\forall \Pi' \in \classPLS: \Pi' \leq \Pi$
$\LocalMaxCut$:
Instance: undirected graph $D=(V,E)$ with edge weights $w: E \to \IR$ with
$S_I \coloneqq \set{(A,B) \sMid A \dcup B = V}$
$c_I((A,B)) \coloneqq w(E(A)) + w(E(B)) \class{tempstep a}{\data{tempstep-from=9}{= w(E) - \sum_{\set{a,b} \in E: a \in A, b \in B}w(\set{a,b})}}$
$N_I((A,B)) \coloneqq \set{(A',B') \in S_I \sMid \exists v \in V: A \Delta A' = \set{v} = B \Delta B'}$
2
1
4
3
2
5
3
2
6
0
\color{var(--red)}A
\color{var(--blue)}B
c_I({\color{var(--red}A},{\color{var(--blue)}B}) = 15
c_I({\color{var(--red}A},{\color{var(--blue)}B}) = 8\phantom{0}
c_I({\color{var(--red}A},{\color{var(--blue)}B}) = 15
c_I({\color{var(--red}A},{\color{var(--blue)}B}) = 18
c_I({\color{var(--red}A},{\color{var(--blue)}B}) = 8\phantom{0}
c_I({\color{var(--red}A},{\color{var(--blue)}B}) = 9\phantom{0}
c_I({\color{var(--red}A},{\color{var(--blue)}B}) = 14
c_I({\color{var(--red}A},{\color{var(--blue)}B}) = 25
Fact 4.19: $\LocalMaxCut$Fact 4.19: is $\classPLS$-complete.
Thm 4.20: Finding PNE in unweighted congestion gamesThm 4.20: is $\classPLS$-complete.
Symmetric Network Congestion Games
N = \set{{\color{var(--green)}1},{\color{var(--blue)}2},{\color{var(--purple)}3}} \small\color{black}x^2 \small\color{black}x^2 \small\color{black}x^2 \small\color{black}1+x \small\color{black}1+x \small\color{black}1 \small\color{black}1+x o
d
\tiny\color{black}1
\tiny\color{black}4
\tiny\color{black}9
\tiny\color{black}1
\tiny\color{black}4
\tiny\color{black}9
\tiny\color{black}1
\tiny\color{black}4
\tiny\color{black}9
\tiny\color{black}2
\tiny\color{black}3
\tiny\color{black}4
\tiny\color{black}2
\tiny\color{black}3
\tiny\color{black}4
\tiny\color{black}1
\tiny\color{black}1
\tiny\color{black}1
\tiny\color{black}2
\tiny\color{black}3
\tiny\color{black}4
o
d
directed graph $D=(V,E)$ with origin $o \in V$ and destination $d \in V$
non-decreasing edge-costs $c_e: \IN \to \IRnn$
⤳ symmetric network congestion game :
set of players $N$
resources $R \coloneqq E$ with resource costs $c_e$
strategies $R(S_i) \coloneqq \set{ P \subseteq E \sMid P \text{ an $o$,$d$-path}}$
Thm. 4.27: In sym. network cong. games a PNE can be computed in poly. time in $\abs{N}$, $\abs{V}$, $\abs{E}$.
in directed graph $D=(V,E)$ with $o,d \in V$
, edge costs $\gamma_e \in \IR$ , edge capacities $\nu_e \in \IRnn$:
static ($o$,$d$-)flow $x = (x_e) \in \IRnn^E$ s.th.
\[\class{tempstep a}{\data{tempstep-from=25}{x_e \leq \nu_e \,\text{ f.a. } e \in E}}
\class{tempstep a}{\data{tempstep-from=26}{\quad\text{and}\quad
\sum_{e=uv \in E}x_e = \sum_{e=vw \in E}x_e \,\text{ f.a. } v \in V \setminus \set{o,d}}}\]
⤳ $\mathrm{cost}(x) \coloneqq \sum_{e \in E} x_e\cdot\gamma_e$ and $\mathrm{value}(x) \coloneqq \sum_{e=ud \in E}x_e - \sum_{e=dw \in E}x_e$
flow $x$ is min-cost flow $\coloniff \forall \text{flow }y: \mathrm{value}(y)=\mathrm{value}(x) \implies \mathrm{cost}(y) \geq \mathrm{cost}(x)$
flow $x$ is integral $\coloniff x \in \INo^E$
Thm. A.11: $\nu \in \INo^E$ and $k \in \INo: \exists \text{flow } x: \mathrm{value}(x) = k$
Successive-Shortest-Path-Algorithm:
Input: $D=(V,E)$, $\gamma \in \INo^E$, $\nu \in \INo^E$, $k \in \INo: \exists \text{flow } x: \mathrm{value}(x) = k$
Output: integral min-cost-flow $x$ of value $k$
Start with zero flow $x$
While $\mathrm{value}(x) \lt k$ Do mm compute cheapest $o$,$d$-path $p$ in residual network wrt. $x$
mm augment $x$ along $p$ as much as possible
Thm. A.12: path-decomposition can be found in poly. time
Matroid Congestion Games
$\mathcal{M}=(R,\mathcal{I})$
matroid $\coloniff R$ a finite set, $\mathcal{I} \subseteq \PSet{R}$ set system s.th.
$\emptyset \in \mathcal{I}$
$\forall I \in \mathcal{I}: \forall J \subseteq I: J \in \mathcal{I}$
$\forall I,J \in \mathcal{I}: \abs{J} \lt \abs{I} \implies \exists r \in I \setminus J: J + r \in \mathcal{I}$
⤳ $I \in \mathcal{I}$ independent sets
$I \in \mathcal{I}$ basis if inclusion-wise maximal ⤳ ${\color{var(--defColor)}\mathcal{B}} \coloneqq \set{I \in \mathcal{I} \sMid I \text{ basis}}$
Thm. 4.31: For $(R,\mathcal{I})$ satisfying matroid axioms (1) and (2) the following are equivalent
$(R,\mathcal{I})$ is matroid
$\forall I,J \in \mathcal{I}: \abs{I} = \abs{J}+1 \implies \exists r \in I \setminus J: J+r \in \mathcal{I}$
$\forall U \subseteq R: \forall I, J \subseteq U$ max. independent in $U \implies \abs{I} = \abs{J}$
⤳ rank of matroid $\mathcal{M}=(R,\mathcal{I})$: $\mathrm{rk}(\mathcal{M}) \coloneqq \abs{B}$ for some basis $B$ of $M$
Thm. 4.32: $(R,\mathcal{I})$ matroid, $B_1,B_2 \in \mathcal{B}$ bases. Then
$\forall r \in B_1 \setminus B_2: \class{tempstep a}{\data{tempstep-from=28}{\exists r' \in B_2 \setminus B_1:}} \class{tempstep a}{\data{tempstep-from=29}{B_1 - r+r' \in \mathcal{B}}}$
Thm. 4.33: $(R,\mathcal{I})$ matroid, $B_1,B_2 \in \mathcal{B}$ bases. Then
$\forall r \in B_1 \setminus B_2: \exists r' \in B_2 \setminus B_1: B_1 - r+r' \in \mathcal{B} \class{tempstep}{\data{tempstep-classes=29-30:hl}{\land B_2 -r'+r \in \mathcal{B}}}$
Lem. 4.34: $(R,\mathcal{I})$ matroid, $B_1,B_2 \in \mathcal{B}$ bases.
Define bipartite graph $D(B_1 \Delta B_2) \coloneqq (V,E)$:
$V \coloneqq B_1 \Delta B_2 \coloneqq B_1 \setminus B_2 \mathbin{\dot{\cup}} B_2 \setminus B_1$
$E \coloneqq \set{(r,r') \sMid r \in B_1, r' \in B_2, B_1-r+r' \in \mathcal{B}}$
Then, $D(B_1 \Delta B_2)$ has perfect matching $M$ , i.e.,
unw. cong. game $G=(N,S,\pi)$ is matroid congestion game if rank $\mathrm{rk}(G) \coloneqq \sum_{i \in N}\mathrm{rk}(\mathcal{M}_i)$
Thm. 4.35: $G$ a matroid congestion game. Then,
Summary: Complexity Results for Unweighted Congestion Games
Unweighted congestion games always have PNE (Thm. 4.5 )
Best-response dynamic in unweighted congestion game can take exponentially many steps (Thm. 4.15 )
Finding soc. opt. PNE in (succinctly represented) unweighted congestion game is NP-complete (Thm. 4.19 )
Finding any PNE in unweighted congestion game is PLS-complete (Thm. 4.26 )
Finding any PNE in (succinctly represented) symmetric network congestion game is possible in polynomial time (Thm. 4.27 )
Best-response dynamic in matroid congestion game takes at most polynomially many steps (Thm. 4.35 )